package day01;

// 二分查找

// 方法一：
//import java.util.ArrayList;
//public class Solution {
//    public int minNumberInRotateArray(int [] array) {
//        int left = 0;
//        int right = array.length-1;
//        // 首先进行判空
//        if(array==null || array.length==0) {
//            return 0;
//        }
//        // 循环判断：
//        while(left < right) {
//            int mid = left + ((right-left)>>1);
//            // 使用右边判断（否则可能会遗漏1 2 2 2 2 2顺序情况）
//            if(array[mid] > array[right]) {
//                // 在右边！
//                left = mid+1;
//            } else if(array[mid] < array[right]) {
//                // 在左边
//                right = mid;
//            } else {
//                // 此时进行线性遍历
//                right--;
//            }
//        }
//        return array[left];
//    }
//}


// 方法二：
//import java.util.ArrayList;
//public class Solution {
//    public int minNumberInRotateArray(int [] array) {
//        // 首先判定是否有元素
//        if(array== null || array.length==0) {
//            return 0;
//        }
//
//        int left = 0;
//        int right = array.length-1;
//        int mid = 0;
//        while(left < right) {
//            if(right - left == 1) {
//                if(array[left] > array[right]) {
//                    mid = right;
//                } else{
//                    mid = left;
//                }
//                break;
//            }
//            // 这里会有一种情况，左中右相等，此时无法判断min是在左or右，则进行线性判断
//
//            mid = left + ((right-left)>>1);
//            if(array[left]==array[right] && array[left]==array[mid]) {
//                // 直接进行线性查找min
//                int ret = array[left];
//                for(int i=left+1; i<right; i++) {
//                    if(ret > array[i]) {
//                        ret = array[i];
//                    }
//                }
//                return ret;
//            }
//
//            if(array[mid] > array[right]) {
//                // 说明此时最小的一定是在mid之后，前面一直在非递减
//                left = mid;
//            } else {
//                // 说明mid及之后是在非递减的，mid及之前一定会存在最小值
//                right = mid;
//            }
//        }
//
//        return array[mid];
//    }
//}



import java.util.ArrayList;
public class Main1 {
        public int minNumberInRotateArray(int [] array) {
            int left = 0;
            int right = array.length-1;
            // 首先进行判空
            if(array==null || array.length==0) {
                return 0;
            }
            // 循环判断：
            while(left < right) {
                int mid = left + ((right-left)>>1);
                // 使用右边判断（否则可能会遗漏1 2 2 2 2 2顺序情况）
                if(array[mid] > array[right]) {
                    // 在右边！
                    left = mid+1;
                } else if(array[mid] < array[right]) {
                    // 在左边
                    right = mid;
                } else {
                    // 此时进行线性遍历
                    right--;
                }
            }
            return array[left];
        }




    public static void main(String[] args) {
        int [] array = {1,2,2,2,2,2};
        Main1 main1 = new Main1();
        int ret = main1.minNumberInRotateArray(array);
        System.out.println(ret);
    }
}



// 其中会有用例无法通过，如1 2 2 2 2 2
// 所以：此时使用右边进行比较

//import java.util.ArrayList;
//public class Solution {
//    public int minNumberInRotateArray(int [] array) {
//        // 首先判定是否有元素
//        if(array== null || array.length==0) {
//            return 0;
//        }
//
//        int left = 0;
//        int right = array.length-1;
//        int mid = 0;
//        while(left < right) {
//            if(right - left == 1) {
//                // 此时后面的值一定是min，因为经过了旋转之后
//                mid = right;
//                break;
//            }
//            // 这里会有一种情况，左中右相等，此时无法判断min是在左or右，则进行线性判断
//
//            mid = left + ((right-left)>>1);
//            if(array[left]==array[right] && array[left]==array[mid]) {
//                // 直接进行线性查找min
//                int ret = array[left];
//                for(int i=left+1; i<right; i++) {
//                    if(ret > array[i]) {
//                        ret = array[i];
//                    }
//                }
//                return ret;
//            }
//
//            if(array[mid] >= array[right]) {
//                // 说明此时最小的一定是在mid之后，前面一直在非递减
//                left = mid;
//            } else {
//                // 说明mid及之后是在非递减的，mid及之前一定会存在最小值
//                right = mid;
//            }
//        }
//
//        return array[mid];
//    }
//}